The present invention relates to a translation look-aside buffer (TLB) control system.
Prior Art and Its Disadvantages
A virtual memory unit used in a virtual addressing system can have a greater memory capacity than, usually several times as great as, that of the actual main memory unit.
To make possible virtual addressing, the virtual memory unit is divided into a plurality of segments, each of which is further subdivided into a plurality of pages, each comprising a prescribed number of bytes.
These pages are allocated for different locations in the whole main memory unit, and for this reason there are prepared page tables reflecting the actual location of each page. This means that one page table reflects the actual locations of all the pages in a specific segment. Accordingly, another page table reflects the actual locations of all the pages pertaining to another segment of the virtual memory unit.
As these page tables are also allocated at random for different segments of the whole main memory unit, there are prepared segment tables reflecting the actual location of each page table.
The segment tables and page tables are retained in the main memory unit, and used for translating a logical address (which may as well be referred to as a virtual address) into a real address, i.e. the actual location of the required page in the main memory unit. Address translation is a process to translate a logical address into an address on the actual main memory unit.
The usual format of a logical address is one of division into three fields represented as the segment number, the page number and the in-page line address. The segment number serves as an index to an entry in the segment table. The segment table entry has a value representing the base address of the page table associated with the segment designated by the segment field. The page number serves as an index to an entry in the page table. The page table entry has a value representing the real address of the page. The in-page line address undergoes no change during address translation and, combined with the page address into which it has been translated, constitues a real address, i.e. an address in the actual main memory unit.
Address translation by referencing these tables is extremely slow, requiring several main memory cycles each time.
For this reason, it is common practice to use, in order to avoid repeating this address translation processing every time the memory unit is searched, a translation look-aside buffer (TLB; also known as an address translation buffer, abbreviated to ATB) in which a plurality of address translation pairs are held, the pairs consisting of the logical addresses most recently referenced and the corresponding real page addresses. This TLB consists of a very fast memory unit, and its use makes it possible to complete an address translation process in a single machine cycle.
Ultra-large computer systems for use in today's huge arrangements require ever greater memory capacities, which keep on increasing for both virtual and main memory units. Virtual memory units are required to have memory capacities on the order of gigabytes (for logical addresses of 30 bits and more) to terabytes (for logical addresses of 40 bits or more). For translation of logical addresses by which to search such a huge virtual memory unit, address translation by three-level look-up or even four-level look-up is contemplated instead of the conventional two-level look-up to segment tables and page tables, resulting in further increasing importance of TLB technology
While the recent progress of LSI technology is significantly decreasing delays due to gate arrays and thereby acceleratedly reducing the machine cycles of ultra-large computers, delays attributable to RAMs constituting memory units, such as those constituting TLB's, or wiring to connect LSI's are more difficult to reduce than gate array-induced delays, so that the machine cycles of the system are determined by delays around these memory units, which constitute a bottle-neck in this respect. Another problem is posed by the expansion of the TLB's themselves invited by the increase of logical addresses, which in turn reflects the increased capacities of virtual memory units.
A TLB may be constituted either fully associatively or set-associatively, the latter using part of the logical address section for referencing.
The U.S. Pat. No. 3,786,427 discloses an example of fully associatively constituted TLB. In such a fully associative TLB (also known as a content addressed memory or CAM), a logical page address to be translated should be compared with every logical page stored in the CAM, so that as many comparators are required as the logical pages stored therein, resulting in the disadvantage of difficulty to expand the CAM capacity. There is another disadvantage that delays in the real address decision path cannot be readily reduced because only one has to be determined out of many real addresses. For this reason, it is usual for more recent supercomputers to use set-associative TLB's.
U.S. Pat. Nos. 4,589,092, 4,638,426 and 4,719,568 disclose examples of this set-associative TLB. Each of these TLB arrangements uses two sets of TLB's (also known as two-way TLB's) to improve its hitting rate, and determines only one real address from one or the other of the two sets. The method used with two-way TLB's is to read out a key address section, which is a part of a logical address registered in each TLB, compare it with the key address section of the logical address whose translation is requested, select and determine the real address directly read out of each TLB, together with the key address, according to the result of comparison. This method of real address determination uses the output of a TLB consisting of a memory unit which is far slower than a gate array, and further requires going through a comparator to generate a real address determination signal. Moreover, as a real address for searching a cache memory has to be selected and determined, this real address determination signal should travel from one LSI to another, there is still another great disadvantage of making it difficult to reduce the machine cycles of an ultra-large computer operating at ultra-high speed machine cycles.
Furthermore, when expanding the TLB's to cope with the increase of logical addresses invited by the expansion of the virtual memory unit, the memory unit is inevitably made slower and the TLB expansion is consequently made more difficult. This at the same time makes it difficult to increase the number (of ways of) TLB's.
In these cases where a plurality of TLB's are used, as disclosed in the aforementioned U.S. Pat. Nos. 4,638,426 and 4,719,568, there is yet another disadvantage of enlarged hardware because, in the absence of the demanded address translation pair, TLB replacement requires the use of hardware employing the least recently used (LRU) algorithm to determine the TLB entry which has remained unused for the longest period.